import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public static boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();

        //以i为结尾的单词是否在字典中
        boolean[] dp = new boolean[len + 1];

        dp[0] = true;

        for (int i = 1; i < len + 1; i++) {
            for (int j = i; j >= 1; j--) {//j为最后一个单词的开头
//                System.out.println(s.substring(j - 1, i));
                if (dp[j - 1] && wordDict.contains(s.substring(j - 1, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

//        System.out.println(Arrays.toString(dp));

        return dp[len];
    }

    public static void main(String[] args) {

        List<String> list = new ArrayList<>();
        list.add("leet");
        list.add("code");

        System.out.println(wordBreak("leetcode", list));
    }
}
